package ninthweek;

import eighthweek.BinaryTreeADT;
import fourthweek.ElementNotFoundException;
import secondweek.EmptyCollectionException;

import java.util.*;

public class ArrayBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T> {

    private static final int DEFAULT_CAPACITY = 50;

    protected int count;
    public T[] tree;//持有数组用于实现堆
    protected int modCount;

    public ArrayBinaryTree(){
        count = 0;
        tree = (T[])new Object[DEFAULT_CAPACITY];
    }

    public ArrayBinaryTree(T element){
        count = 1;
        tree = (T[])new Object[DEFAULT_CAPACITY];
        tree[0] = element;
    }

    protected void expandCapacity(){
        tree=Arrays.copyOf(tree, tree.length*2);
    }

    @Override
    public T getRootElement() throws EmptyCollectionException {
        if(isEmpty()){
            throw new EmptyCollectionException("ArrayBinaryTree");
        }
        return tree[0];
    }

    @Override
    public boolean isEmpty() {
        return count==0;
    }

    @Override
    public int size() {
        return count;
    }

    @Override
    public boolean contains(T targetElement) {
        T temp;
        boolean found = false;

        try{
            temp = find(targetElement);
            found = true;
        }catch(Exception ElementNotFoundException){
            found = false;
        }

        return found;
    }

    @Override
    public T find(T targetElement) throws ElementNotFoundException {

        T temp = null;
        boolean found = false;

        for(int i=0;i<tree.length;i++){
            if(tree[i]!=null){
                if(targetElement.equals(tree[i])){
                    found = true;
                    temp=tree[i];
                }

            }
        }

        if(!found){
            throw new ElementNotFoundException("ArrayBinaryTree");
        }

        return temp;
    }

    @Override
    public String toString() {
        ArrayList<T> tempList = new ArrayList<T>();
        ///用于临时存储连理获取的对象的引用的队列
        levelOrder(0,tempList);
        return tempList.toString();
    }

    @Override
    public Iterator<T> iterator() {
        return this.iteratorInOrder();
    }

    public Iterator<T> iteratorInOrder() {
        ArrayList<T> tempList = new ArrayList<>();
        inOrder(0, tempList);
        return new TreeIterator(tempList.iterator());
    }

    protected void inOrder(int root,ArrayList<T> tempList){
        if(root<tree.length){
            if(tree[root]!=null){
                inOrder(root*2+1, tempList);
                tempList.add(tree[root]);
                inOrder(root*2+2, tempList);
            }
        }
    }

    protected void levelOrder(int root,ArrayList<T> tempList){
        int temp = root;
        while(tree[temp] != null){
            tempList.add(tree[temp]);
            temp++;
        }
    }

    @Override
    public Iterator<T> iteratorPreOrder() {
        ArrayList<T> tempList = new ArrayList<>();
        PreOrder(0, tempList);
        return new TreeIterator(tempList.iterator());
    }

    protected void PreOrder(int root,ArrayList<T> tempList){
        if(root<tree.length){
            if(tree[root]!=null){
                tempList.add(tree[root]);
                PreOrder(root*2+1, tempList);
                PreOrder(root*2+2, tempList);
            }
        }
    }

    @Override
    public Iterator<T> iteratorPostOrder() {
        ArrayList<T> tempList = new ArrayList<>();
        PostOrder(0, tempList);
        return new TreeIterator(tempList.iterator());
    }

    protected void PostOrder(int root,ArrayList<T> tempList){
        if(root<tree.length){
            if(tree[root]!=null){
                PostOrder(root*2+1, tempList);
                PostOrder(root*2+2, tempList);
                tempList.add(tree[root]);
            }
        }
    }

    @Override
    public Iterator<T> iteratorLevelOrder() {
        // TODO Auto-generated method stub
        return null;
    }


    /**
     * 自定义一个TreeIterator类
     * @author MrLBZ
     *
     */
    private class TreeIterator implements Iterator<T>
    {
        private int expectedModCount;
        private Iterator<T> iter;

        public TreeIterator(Iterator<T> iter)
        {
            this.iter = iter;
            expectedModCount = modCount;
        }

        /**
         * Returns true if this iterator has at least one more element
         * to deliver in the iteration.
         *
         * @return  true if this iterator has at least one more element to deliver
         *          in the iteration
         * @throws  ConcurrentModificationException if the collection has changed
         *          while the iterator is in use
         */
        public boolean hasNext() throws ConcurrentModificationException
        {
            if (!(modCount == expectedModCount))
                throw new ConcurrentModificationException();

            return (iter.hasNext());
        }

        /**
         * Returns the next element in the iteration. If there are no
         * more elements in this iteration, a NoSuchElementException is
         * thrown.
         *
         * @return the next element in the iteration
         * @throws NoSuchElementException if the iterator is empty
         */
        public T next() throws NoSuchElementException
        {
            if (hasNext())
                return (iter.next());
            else
                throw new NoSuchElementException();
        }

        /**
         * The remove operation is not supported.
         *
         * @throws UnsupportedOperationException if the remove operation is called
         */
        public void remove()
        {
            throw new UnsupportedOperationException();
        }
    }
}
